from typing import List, Optional

from leetcode4p.com.siyuan.ListNode import ListNode


class Solution:
    '''归并二分法'''

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        return self.merge(0, len(lists) - 1, lists)

    def merge(self, i, j, lists: List[Optional[ListNode]]):
        if i == j:
            return lists[i]

        if i > j:
            return None
        mid = int((i + j) / 2)
        return self.mergeTwo(self.merge(i, mid, lists), self.merge(mid + 1, j, lists))

    '''两两合并'''

    def mergeTwo(self, list1: ListNode, list2: ListNode):
        res = ListNode(0)

        tmp = res
        while list1 or list2:
            if not list1:
                tmp.next = list2
                break
            elif not list2:
                tmp.next = list1
                break
            elif list1.val < list2.val:
                tmp.next = ListNode(list1.val)
                list1 = list1.next
            else:
                tmp.next = ListNode(list2.val)
                list2 = list2.next
            tmp = tmp.next

        return res.next

if __name__ == '__main__':
    list1 = ListNode(1)
    list1.next = ListNode(4)
    list1.next.next = ListNode(5)

    list2 = ListNode(1)
    list2.next = ListNode(3)
    list2.next.next = ListNode(4)

    list3 = ListNode(2)
    list3.next = ListNode(6)

    lists = [list1, list2, list3]
    sl = Solution()
    res = sl.mergeKLists(lists)
    while res:
        print(res.val)
        res = res.next
